#include <stdlib.h>
#include <stdio.h>
#include "avl.h"

#define height(x) ((x) ? (x) -> height : 0)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define update(rt) rt -> height = max(height(rt -> left), height(rt -> right)) + 1

void LL(node_t **root) {
    node_t* rt = *root;
    node_t* lson = *root = rt -> left;
    rt -> left = lson -> right;
    lson -> right = rt;
    update(rt); update(lson);
}

void RR(node_t **root) {
    node_t* rt = *root;
    node_t* rson = *root = rt -> right;
    rt -> right = rson -> left;
    rson -> left = rt;
    update(rt); update(rson);
}

void RL(node_t **root) { LL(&((*root) -> right)); RR(root); }
void LR(node_t **root) { RR(&((*root) -> left)); LL(root); }

node_t* create_node(int val) {
    node_t *rt = (node_t*) malloc(sizeof(node_t));
    rt -> val = val;
    rt -> left = rt -> right = rt -> parent = NULL;
    rt -> height = 1;
    return rt;
}

node_t* avl_insert(node_t *root, int val){
    if(!root) {
        root = create_node(val);
        return root;
    }
    if(val < root -> val){
        root -> left = avl_insert(root -> left, val);
        if(height(root -> left) > height(root -> right) + 1)
            val < root -> left -> val ? LL(&root) : LR(&root);
    } else {
        root -> right = avl_insert(root -> right, val);
        if(height(root -> right) > height(root -> left) + 1)
            val > root -> right -> val ? RR(&root) : RL(&root);
    }
    update(root);
    return root;
}